package 中等.其他;

import java.util.*;

/**
 * 给定一个长度为偶数的整数数组 arr，只有对 arr 进行重组后可以满足 “对于
 * 每个 0 <= i < len(arr) / 2，都有 arr[2 * i + 1] = 2 * arr[2 * i]” 时，
 * 返回 true；否则，返回 false。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/array-of-doubled-pairs
 */
public class 二倍数对数组_954 {

    public static void main(String[] args) {

        int[] arr = {4, -2, 2, -4};
        System.out.println(canReorderDoubled2(arr));

    }

    /**
     * 哈希表+排序+一次遍历
     * 使用一个 map 存储数字出现的次数
     * 如果之前的值存在 cur/2 或者 cur*2 ，那么存在一对二倍数
     * 将之前存储的二倍数移除，否则将 cur 放入 map，并将数量+1
     *
     * @param arr
     * @return
     */
    public static boolean canReorderDoubled(int[] arr) {
        Map<Integer, Integer> cnt = new HashMap<Integer, Integer>();
        for (int x : arr) {
            cnt.put(x, cnt.getOrDefault(x, 0) + 1);
        }
        if (cnt.getOrDefault(0, 0) % 2 != 0) {
            return false;
        }
        Arrays.sort(arr);  // 需要排序，优先将num/2的数匹配掉
        Map<Integer, Integer> map = new HashMap();
        int count = 0;
        for (int num : arr) {
            if (num % 2 == 0 && map.getOrDefault(num / 2, 0) > 0) {
                count++;
                map.put(num / 2, map.get(num / 2) - 1);
            } else if (map.getOrDefault(num * 2, 0) > 0) {
                count++;
                map.put(num * 2, map.get(num * 2) - 1);
            } else {
                map.put(num, map.getOrDefault(num, 0) + 1);
            }
        }
        return count == arr.length / 2;
    }

    /**
     * 哈希表+排序+预处理剪枝
     * 先遍历将所有数字出现的次数统计
     * 1，0只能和0进行二倍数匹配，如果为奇数，直接返回false
     * 2，二倍数和正负无关，直接统计绝对值
     * 3，如果存在 arr.length/2 对二倍数，那么num的数量和num*2的数量一定是相等的
     *
     * @param arr
     * @return
     */
    public static boolean canReorderDoubled2(int[] arr) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int num : arr) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        if (map.getOrDefault(0, 0) % 2 == 1) {
            return false;
        }
        List<Integer> list = new ArrayList<>();
        for (Integer num : map.keySet()) {
            list.add(num);
        }

        // -2 -4 ... 使用绝对值排序
        list.sort((o1, o2) -> Math.abs(o1) - Math.abs(o2));  //负数要将大的数排在前面，保证*2的值存在

        for (Integer num : list) {
            if (map.getOrDefault(num, 0) == 0) {
                continue;
            }
            if (map.getOrDefault(num * 2, 0) < map.get(num)) {
                return false;
            }
            // 1 2 4 数字
            // 1 2 1 数量，这里不能直接置为0，有可能后面的数字可以和 num*2 匹配
            map.put(num * 2, map.get(num * 2) - map.get(num));
        }
        return true;
    }

}
